Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Tree
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Level Order Traversal Pattern (easy)
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Tree Depth Pattern (easy)
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Minimum Depth of a Binary Tree

Problem Statement

Given a root of the binary tree, find the minimum depth of a binary tree.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Examples

Example 1

Image

Example 2

Image

Constraints:

  • The number of nodes in the tree is in the range [0, 105].
  • -1000 <= Node.val <= 1000

Solution

To solve this problem, we use a Breadth-First Search (BFS) approach to find the minimum depth of a binary tree. BFS is ideal for this problem because it explores nodes level by level, ensuring that we find the closest leaf node (node without children) to the root as quickly as possible.

Starting from the root, we traverse the tree level by level, and for each node, we check if it is a leaf node. The moment we encounter the first leaf node, we return the depth of that node as it represents the minimum depth of the tree. By using a queue to keep track of nodes at each level, we can efficiently manage this traversal.

Step-by-Step Algorithm

  1. Check if the tree is empty:

    • If the root is null, return 0 as the tree has no depth.
  2. Initialize the BFS queue:

    • Create an empty queue and add the root node to it.
    • Initialize a variable minimumTreeDepth to 0 to keep track of the depth as we traverse each level.
  3. Start BFS traversal:

    • While the queue is not empty, perform the following steps:
      • Increment the minimumTreeDepth by 1 to account for the current level.
      • Determine the number of nodes at the current level by checking the size of the queue.
  4. Process each node at the current level:

    • For each node in the current level, perform the following:
      • Dequeue the node from the queue.
      • Check if the node is a leaf node (both left and right children are null).
      • If it is a leaf node, return the current minimumTreeDepth as this is the minimum depth of the tree.
  5. Add children to the queue:

    • If the node is not a leaf, add its left and right children to the queue (if they exist) to be processed in the next level.
  6. Repeat until the queue is empty:

    • Continue processing each level until the queue is empty, which indicates that all nodes have been traversed. The first leaf node encountered will provide the minimum depth.

Algorithm Walkthrough

Image
  1. Initialization:

    • Start with the root node 12.
    • Initialize an empty queue and add the root node 12 to it.
    • Set minimumTreeDepth to 0.
  2. Start BFS Traversal:

    • The queue contains [12].
    • Increment minimumTreeDepth to 1 because we are starting at the first level.
  3. Process the first level (root node 12):

    • The size of the queue is 1, indicating one node at this level.
    • Dequeue node 12 from the queue.
    • Check if node 12 is a leaf node (both left and right children are null):
      • Node 12 is not a leaf node, as it has left and right children.
    • Add the left child 7 and the right child 1 of node 12 to the queue.
    • The queue now contains [7, 1].
  4. Process the second level (nodes 7 and 1):

    • The queue contains [7, 1].

    • Increment minimumTreeDepth to 2 because we are moving to the second level.

    • The size of the queue is 2, indicating two nodes at this level.

    • Processing node 7:

      • Dequeue node 7 from the queue.
      • Check if node 7 is a leaf node:
        • Node 7 is a leaf node (no left or right children).
      • Since node 7 is a leaf node, return the current minimumTreeDepth, which is 2.

Final Output: The minimum depth of the tree [12, 7, 1, null, null, 10, 5] is 2.

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be which is required for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.

Similar Problems

Problem 1: Given a binary tree, find its maximum depth (or height) using Tree BFS traversal.

Solution: We will follow a similar approach. Instead of returning as soon as we find a leaf node, we will keep traversing for all the levels, incrementing maximumDepth each time we complete a level. Here is what the code will look like:

Here is the visual representation of the algorithm:

Image

Code

Here is the code for this algorithm:

Java

. . . .

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be which is required for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.

Minimum Depth of a Binary Tree (easy)
Balanced Binary Tree (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity

Similar Problems

Code

Complexity Analysis

Time Complexity

Space Complexity